#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;

int getRandom(int left,int right)
{
    int i = rand()%(right-left+1)+left;

    return i; 
}

void qsort(vector<int>& arr,int l,int r)
{
    if(l>=r) return;
    int left=l-1;
    int right=r+1;
    int key = arr[getRandom(l,r)];
    int i = l;
    while(i<right)
    {
        if(arr[i]<key)
            swap(arr[++left],arr[i++]);
        else if(arr[i]==key)
            i++;
        else
            swap(arr[--right],arr[i]);
    }
    qsort(arr,l,left);
    qsort(arr,right,r);
}

int main(){
    srand(time(NULL));
    vector<int> arr = {8,4,5,7,1,2,3,9,6,0};
    for(auto e:arr)
        cout<<e<<' ';
    qsort(arr,0, arr.size()-1);
    cout<<endl;
    for(auto e:arr)
        cout<<e<<' ';
    return 0;
}